package 动态规划;

import java.util.ArrayList;
import java.util.List;

public class pCC31三角形 {
    public int minimumTotal1(ArrayList<ArrayList<Integer>> triangle) {
        //动态规划思路：自上而下
        if (triangle.isEmpty()) {
            return 0;
        }

        ArrayList< ArrayList<Integer> > minPathSum=new ArrayList<>();
        for (int i = 0; i <triangle.size(); i++) {
            minPathSum.add(new ArrayList<>());  //初始化二维数组 minPathSum
        }

        minPathSum.get(0).add(triangle.get(0).get(0)); //保存第一行 F(0,0)的值

        for (int i = 1; i <triangle.size(); i++) {
            //从第二行开始，处理每一行的各个元素
            int curSum=0;

            for (int j = 0; j <=i; j++) {
                if (j==0) {
                    //处理每一行的第一列
                    curSum=minPathSum.get(i-1).get(0);
                }else if(j==i) {
                    //处理每一行的最后一列
                    curSum=minPathSum.get(i-1).get(i-1);
                }else {
                    //处理每一行中间元素
                    curSum=Math.min( minPathSum.get(i-1).get(j-1),minPathSum.get(i-1).get(j));
                }
                minPathSum.get(i).add( triangle.get(i).get(j)+curSum );
            }

        }
        //查找 minPathSum二维数组中的最后一个列表中的最小元素
        int size=triangle.size();
        int minSum=Integer.MAX_VALUE;
        for (int i = 0; i<size;i++) {
            minSum=Math.min(minPathSum.get(size-1).get(i),minSum);
        }

        return minSum;
    }

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        //动态规划思路：从下到上
        if (triangle.isEmpty()) {
            return 0;
        }

        ArrayList< ArrayList<Integer> > minSum=new ArrayList<>(triangle);
        int row=triangle.size();

        for (int i = row-2; i >=0; i--) {
            //从倒数第二行开始
            for (int j = 0; j <=i; j++) {
                int curSum=Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1)) + triangle.get(i).get(j);
                minSum.get(i).set(j,curSum);
            }
        }
        return minSum.get(0).get(0);
    }
}
